import java.util.Arrays;

public class Num16 {
    //给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
    public static void main(String[] args) {
        int[] nums = new int[]{0,3,97,102,200};
        Num16 num16 = new Num16();
        System.out.println(num16.threeSumClosest(nums, 300));
    }
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length == 3) return nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        int sum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int l = i + 1;
            int r = nums.length - 1;
            while (l != r) {
                int res = nums[i] + nums[l] + nums[r];
                if (Math.abs(sum - target) > Math.abs(res - target)) {
                    sum = res;
                }
                if (res > target) {
                    r--;
                    while (l != r && nums[r] == nums[r + 1]) {
                        r--;
                    }
                } else {
                    l++;
                    while (l != r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                }
            }
            while (i < nums.length - 2 && nums[i] == nums[i + 1]) i++;
        }
        return sum;
    }
}
